#include <stdio.h>
#include <conio.h>
int heap[20],it;

void heapify(int n,int item)
{
    int ptr=n+1,par;
    while(ptr>1)
    {
      par=(int)(ptr/2);
      if(item <= heap[par])
      {
	heap[ptr]=item;
	return;
      }
      heap[ptr]=heap[par];
      ptr=par;
    }
    heap[1]=item;
    return;
}

void delete(int n)
{
   int ptr=1,last,left=2,right=3;
   last=heap[n];
   it=heap[1];
   n--;
   while(right <= n)
   {
      if(last >= heap[right] && last >= heap[left])
      {
	 heap[ptr]=last;
	 return;
      }
   if(heap[left] <= heap[right])
   {
       heap[ptr]=heap[right];
       ptr=right;
   }
   else
   {
     heap[ptr]=heap[left];
     ptr=left;
   }
   left=2*ptr;
   right=left+1;
  }
  if (left==n && last<=heap[left])
  {
    heap[ptr]=heap[left];
    ptr=left;
  }
  heap[ptr]=last;
}


void main()
{
    int i,n,j,item;
    clrscr();
    printf("--- HEAPSORT ---\n");
    printf("No. of elements: ");
    scanf("%d",&n);
    printf("\nList Input\n");
    for(i=1;i<=n;i++)
      scanf("%d",&heap[i]);

    for(i=1;i<=n-1;i++)
     heapify(i,heap[i+1]);
    for(j=n;j>1;j--)
    {
      delete(j);
      heap[j+1]=it;
    }

    printf("\nSorted List\n");
    for(i=2;i<=n+1;i++)
     printf("%d\t",heap[i]);
    getch();
}


